#include <bits/stdc++.h>
using namespace std;


void getNext(int next[],string m){
	int j = 0;
	next[0] = 0;
	for(int i = 0;i < m.size();i++){
		while(m[i] != m[j] && j > 0){
			j = next[j-1];
		}
		if(m[i] == m[j]){
			j++;
		}
		next[i] = j;
	}
}

int KMP(string s,string m){
	if(m.size() == 0){
		return 0;
	}
	int *next = new int[m.size()];
	getNext(next,m);
	int j = 0;
	for(int i = 0;i < s.size();i++){
		while(s[i] != m[j] && j > 0){
			j = next[j-1];
		}
		if(s[i] == m[j]){
			j++;
		}
		if(j == m.size()) return i - j + 1;
	}
	return -1;
}

int main(){
	
	return 0;
}
